#include<bits/stdc++.h>
using namespace std;
struct ios{
    inline char gc(){
        static const int IN_LEN=1<<18|1;
        static char buf[IN_LEN],*s,*t;
        return (s==t)&&(t=(s=buf)+fread(buf,1,IN_LEN,stdin)),s==t?-1:*s++;
    }
    template <typename _Tp> inline ios & operator >> (_Tp&x){
        static char ch,sgn; ch = gc(), sgn = 0;
        for(;!isdigit(ch);ch=gc()){if(ch==-1)return *this;sgn|=ch=='-';}
        for(x=0;isdigit(ch);ch=gc())x=x*10+(ch^'0');
        sgn&&(x=-x); return *this;
    }
}io;
#define cin io
int T;
int n,m;
int fa[100011],L[100011],R[100011];
int find(int x)
{
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}
int Merge(int x,int y)
{
	if(!x || !y)
		return x|y;
	x = find(x),y = find(y);
	if(x == y)
		return x;
	fa[y] = x;
	L[x] = Merge(L[x],L[y]),R[x] = Merge(R[x],R[y]);
	return x;
}
vector<int> In[100011],Out[100011];
int nxt[100011];
int dui[100011];
int cnt;
int cir,cnt_l,s_l;
bool vis[100011],lk[100011];
void DFS(int p,int dep)
{
	vis[p] = 1;
	if(!nxt[p])
		return cnt_l++,s_l += dep,void();
	if(vis[nxt[p]])
		return cir = __gcd(cir,dep),void();
	DFS(nxt[p],dep + 1);
}
int main()
{
	freopen("circ.in","r",stdin);
	freopen("circ.out","w",stdout);
	cin >> T;
	while(T--)
	{
		cin >> n >> m;
		for(int i = 1;i <= n;i++)
			fa[i] = i,In[i].clear(),Out[i].clear(),nxt[i] = L[i] = R[i] = vis[i] = lk[i] = 0;
		for(int i = 1;i <= m;i++)
		{
			int x,y;
			cin >> x >> y;
			x++,y++;
			Out[x].push_back(y),In[y].push_back(x);
		}
		for(int p = 1;p <= n;p++)
		{
			if(!In[p].empty())
				L[p] = In[p][0];
			if(!Out[p].empty())
				R[p] = Out[p][0];
		}
		for(int p = 1;p <= n;p++)
		{
			for(int i = 1;i < In[p].size();i++)
				L[p] = Merge(L[p],In[p][i]);
			for(int i = 1;i < Out[p].size();i++)
				R[p] = Merge(R[p],Out[p][i]);
		}
		cnt = 0;
		for(int i = 1;i <= n;i++) if(fa[i] == i)
			dui[i] = ++cnt;
		for(int p = 1;p <= n;p++)
			if(!Out[p].empty() && !nxt[dui[find(p)]])
				nxt[dui[find(p)]] = dui[find(Out[p][0])],lk[dui[find(Out[p][0])]] = 1;
		cir = cnt_l = s_l = 0;
		for(int i = 1;i <= cnt;i++) if(!lk[i])
			DFS(i,1);
		for(int i = 1;i <= cnt;i++) if(!vis[i])
			DFS(i,1);
		if(cir)
			cout << n - cir << "\n";
		else
			cout << n - s_l + cnt_l << "\n";
	}
	return 0;
}
